package com.da.javatest.niuke.baodian;

import java.util.ArrayList;
import java.util.List;

import com.da.javatest.niuke.common.ListNode;

/**
 * @author chenlida
 * @date 2020/10/4 23:26
 * https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C11Partition {
    public ListNode partition(ListNode pHead, int x) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        ListNode head = pHead;

        do {
            int val = head.val;
            if (val < x) {
                l1.add(val);
            } else {
                l2.add(val);
            }
            head = head.next;
        } while (head != null);
        l1.addAll(l2);

        head = pHead;
        for (Integer val : l1) {
            head.val = val;
            head = head.next;
        }
        return pHead;
    }

    /**
     * 定小数链表和大数链表，最后完成后将两链表连接，注意头结点也有值，需要进行比较
     */
    public ListNode partition2(ListNode pHead, int x) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode cur = pHead;
        ListNode Shead = new ListNode(-1);
        ListNode Bhead = new ListNode(-1);
        ListNode Stmp = Shead;
        ListNode Btmp = Bhead;
        while (cur != null) {
            if (cur.val < x) {
                Stmp.next = new ListNode(cur.val);
                Stmp = Stmp.next;
            } else {
                Btmp.next = new ListNode(cur.val);
                Btmp = Btmp.next;
            }
            cur = cur.next;
        }
        cur = Shead;
        while (cur.next != null && cur.next.val != -1) {
            cur = cur.next;
        }
        cur.next = Bhead.next;
        return Shead.next;
    }

}
